#include <bits/stdc++.h>
using namespace std;
namespace IO
{ 
	char Is[(1<<21)+10],Os[(1<<21)+10];
	int Ipt,Opt;
	char gc()
	{
		if(Ipt==1<<21)Ipt=0;
		if(!Ipt){Is[fread(Is,1,1<<21,stdin)]=0;}
		return Is[Ipt++];
	}
	void flush(){fwrite(Os,1,Opt,stdout);Opt=0;}
	void pc(char x)
	{
		if(Opt==1<<21)flush();
		Os[Opt++]=x;
	}
	int read()
	{
		int x=0;char ch=gc();while(ch<'0'||ch>'9')ch=gc();while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=gc();return x;
	}
}
using namespace IO;
